<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.9.0">
    

    

    



    <meta charset="utf-8">
    
    
    <meta name="sogou_site_verification" content="true">
    
    
    
    <title>红黑树的变色与旋转 | Lvshen&#39;s Blog | This is My World</title>
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    
    <meta name="theme-color" content="#3F51B5">
    
    
    <meta name="keywords" content="算法,红黑树">
    <meta name="baidu-site-verification" content="VIVNdSiMZm">
    <meta name="description" content="为什么需要红黑树？二叉查找树红黑树需要根据二叉查找树的规则生成，那么二叉查找树具备什么特性呢？其特性如下：  左子树上所有结点的值均小于或等于它的根结点的值。 右子树上所有结点的值均大于或等于它的根结点的值。 左、右子树也分别为二叉排序树。">
<meta name="keywords" content="算法,红黑树">
<meta property="og:type" content="article">
<meta property="og:title" content="红黑树的变色与旋转">
<meta property="og:url" content="https://lvshen9.gitee.io/2017/11/07/红黑树的变色与旋转/index.html">
<meta property="og:site_name" content="Lvshen&#39;s Blog">
<meta property="og:description" content="为什么需要红黑树？二叉查找树红黑树需要根据二叉查找树的规则生成，那么二叉查找树具备什么特性呢？其特性如下：  左子树上所有结点的值均小于或等于它的根结点的值。 右子树上所有结点的值均大于或等于它的根结点的值。 左、右子树也分别为二叉排序树。">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/ffe9a82dac264f219da292caf72aaf99.png">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/4f4ccb81bd4a43a4b323158e50894e10.jpeg">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/27f5eb454f154312a2bd836c31366d1c.jpeg">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/e6f6470412064018ab4985574ccf9b42.jpeg">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/b33dd4fe9fa1406483100fc8d94756e9.png">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/e2c8a86adfdf4c038dfab611a32fca2b.jpeg">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/59ab2094d6b74da3bbb4f26629521b00.png">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/1888aa1672284d94af7b731ffe72257e.png">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/12a8cd12919f4b99a2254beda609e5bf.png">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/ad6dddf3ed144c5b979183f13c290cc2.jpeg">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/12d9f1e3b7d1446daa1b8d1a48897cde.jpeg">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/74f6f8f8355247948495b4b3094f86bc.png">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/d69e7b48a28f4135a7554c360b0bea5b.jpeg">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/4b323ee47f9d46b781b0ce204d0b79af.jpeg">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/4ae94e8a07044050bed14496231392f2.jpeg">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/5809321e3f774a578536d629a79b605d.png">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/c0adf7a0db354d2e874343c16f18f422.jpeg">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/d169722adeef4be094064d5dde40d409.jpeg">
<meta property="og:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/e79b3c4ba10d45d78e281134d454fdbe.jpeg">
<meta property="og:updated_time" content="2017-11-07T06:43:42.638Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="红黑树的变色与旋转">
<meta name="twitter:description" content="为什么需要红黑树？二叉查找树红黑树需要根据二叉查找树的规则生成，那么二叉查找树具备什么特性呢？其特性如下：  左子树上所有结点的值均小于或等于它的根结点的值。 右子树上所有结点的值均大于或等于它的根结点的值。 左、右子树也分别为二叉排序树。">
<meta name="twitter:image" content="http://5b0988e595225.cdn.sohucs.com/images/20171102/ffe9a82dac264f219da292caf72aaf99.png">
    
    <link rel="shortcut icon" href="/img/mylogo.jpg">
    <link rel="stylesheet" href="//unpkg.com/hexo-theme-material-indigo@latest/css/style.css">
    <script>window.lazyScripts=[]</script>

    <!-- custom head -->
    

</head>

<body>
    <div id="loading" class="active"></div>

    <aside id="menu" class="hide" >
  <div class="inner flex-row-vertical">
    <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menu-off">
        <i class="icon icon-lg icon-close"></i>
    </a>
    <div class="brand-wrap" style="background-image:url(/img/brand.jpg)">
      <div class="brand">
        <a href="/" class="avatar waves-effect waves-circle waves-light">
          <img src="/img/avatar.jpg">
        </a>
        <hgroup class="introduce">
          <h5 class="nickname">我的技术小房间</h5>
          <a href="mailto:https://lvshen9.github.io" title="https://lvshen9.github.io" class="mail">https://lvshen9.github.io</a>
        </hgroup>
      </div>
    </div>
    <div class="scroll-wrap flex-col">
      <ul class="nav">
        
            <li class="waves-block waves-effect">
              <a href="/"  >
                <i class="icon icon-lg icon-home"></i>
                主页
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/archives"  >
                <i class="icon icon-lg icon-archives"></i>
                Archives
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/tags"  >
                <i class="icon icon-lg icon-tags"></i>
                Tags
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/categories"  >
                <i class="icon icon-lg icon-th-list"></i>
                Categories
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/about"  >
                <i class="icon icon-lg icon-address-book"></i>
                About
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/collection"  >
                <i class="icon icon-lg icon-apple"></i>
                Collection
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://lvshen9.github.io/" target="_blank" >
                <i class="icon icon-lg icon-wordpress"></i>
                Blog
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://github.com/lvshen9" target="_blank" >
                <i class="icon icon-lg icon-github-alt"></i>
                GitHub
              </a>
            </li>
        
      </ul>
    </div>
  </div>
</aside>

    <main id="main">
        <header class="top-header" id="header">
    <div class="flex-row">
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light on" id="menu-toggle">
          <i class="icon icon-lg icon-navicon"></i>
        </a>
        <div class="flex-col header-title ellipsis">红黑树的变色与旋转</div>
        
        <div class="search-wrap" id="search-wrap">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="back">
                <i class="icon icon-lg icon-chevron-left"></i>
            </a>
            <input type="text" id="key" class="search-input" autocomplete="off" placeholder="输入感兴趣的关键字">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="search">
                <i class="icon icon-lg icon-search"></i>
            </a>
        </div>
        
        
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menuShare">
            <i class="icon icon-lg icon-share-alt"></i>
        </a>
        
    </div>
</header>
<header class="content-header post-header">

    <div class="container fade-scale">
        <h1 class="title">红黑树的变色与旋转</h1>
        <h5 class="subtitle">
            
                <time datetime="2017-11-07T06:06:49.000Z" itemprop="datePublished" class="page-time">
  2017-11-07
</time>


	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/技术/">技术</a></li></ul>

            
        </h5>
    </div>

    


</header>


<div class="container body-wrap">
    
    <aside class="post-widget">
        <nav class="post-toc-wrap post-toc-shrink" id="post-toc">
            <h4>TOC</h4>
            <ol class="post-toc"><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#为什么需要红黑树？"><span class="post-toc-number">1.</span> <span class="post-toc-text">为什么需要红黑树？</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#二叉查找树"><span class="post-toc-number">1.1.</span> <span class="post-toc-text">二叉查找树</span></a></li><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#二叉查找树的缺点"><span class="post-toc-number">1.2.</span> <span class="post-toc-text">二叉查找树的缺点</span></a></li></ol></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#红黑树的特性"><span class="post-toc-number">2.</span> <span class="post-toc-text">红黑树的特性</span></a></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#调整方法"><span class="post-toc-number">3.</span> <span class="post-toc-text">调整方法</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#变色"><span class="post-toc-number">3.1.</span> <span class="post-toc-text">变色</span></a></li><li class="post-toc-item post-toc-level-5"><a class="post-toc-link" href="#旋转"><span class="post-toc-number">3.2.</span> <span class="post-toc-text">旋转</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-6"><a class="post-toc-link" href="#左旋转"><span class="post-toc-number">3.2.1.</span> <span class="post-toc-text">左旋转</span></a></li><li class="post-toc-item post-toc-level-6"><a class="post-toc-link" href="#右旋转"><span class="post-toc-number">3.2.2.</span> <span class="post-toc-text">右旋转</span></a></li></ol></li></ol></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#实战举栗子"><span class="post-toc-number">4.</span> <span class="post-toc-text">实战举栗子</span></a></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#红黑树使用场景"><span class="post-toc-number">5.</span> <span class="post-toc-text">红黑树使用场景</span></a></li></ol>
        </nav>
    </aside>


<article id="post-红黑树的变色与旋转"
  class="post-article article-type-post fade" itemprop="blogPost">

    <div class="post-card">
        <h1 class="post-card-title">红黑树的变色与旋转</h1>
        <div class="post-meta">
            <time class="post-time" title="2017-11-07 14:06:49" datetime="2017-11-07T06:06:49.000Z"  itemprop="datePublished">2017-11-07</time>

            
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/技术/">技术</a></li></ul>



            
<span id="busuanzi_container_page_pv" title="文章总阅读量" style='display:none'>
    <i class="icon icon-eye icon-pr"></i><span id="busuanzi_value_page_pv"></span>
</span>


        </div>
        <div class="post-content" id="post-content" itemprop="postContent">
            <h4 id="为什么需要红黑树？"><a href="#为什么需要红黑树？" class="headerlink" title="为什么需要红黑树？"></a>为什么需要红黑树？</h4><h5 id="二叉查找树"><a href="#二叉查找树" class="headerlink" title="二叉查找树"></a>二叉查找树</h5><p>红黑树需要根据二叉查找树的规则生成，那么二叉查找树具备什么特性呢？其特性如下：</p>
<ol>
<li>左子树上所有结点的值均小于或等于它的根结点的值。</li>
<li>右子树上所有结点的值均大于或等于它的根结点的值。</li>
<li>左、右子树也分别为二叉排序树。</li>
</ol>
<a id="more"></a>
<h5 id="二叉查找树的缺点"><a href="#二叉查找树的缺点" class="headerlink" title="二叉查找树的缺点"></a>二叉查找树的缺点</h5><p>如果我们在二叉查找树中插入某个值，可能会出现如下一种情况：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/ffe9a82dac264f219da292caf72aaf99.png" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<p>这样线性的结构大大影响了查找性能，这是就需要红黑树。</p>
<h4 id="红黑树的特性"><a href="#红黑树的特性" class="headerlink" title="红黑树的特性"></a>红黑树的特性</h4><p>红黑树是一种自平衡的二叉查找树，它在二叉查找树的基础上又具备如下特征：</p>
<ol>
<li>节点是红色或黑色。</li>
<li>根节点是黑色。</li>
<li>每个叶子节点都是黑色的空节点（NIL节点）。</li>
<li>每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)</li>
<li>从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。</li>
</ol>
<p>如下图，就是一颗典型的红黑树：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/4f4ccb81bd4a43a4b323158e50894e10.jpeg" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<p>为了满足如上的规则，实现结构的平衡，我们在插入或删除节点的时候，就需要做一些相应的调整。</p>
<p>例如：</p>
<p>1.向原红黑树插入值为14的新节点：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/27f5eb454f154312a2bd836c31366d1c.jpeg" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<p>2.向原红黑树插入值为21的新节点：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/e6f6470412064018ab4985574ccf9b42.jpeg" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<p>由于父节点22是红色节点，因此这种情况打破了红黑树的规则4（每个红色节点的两个子节点都是黑色），必须进行调整，使之重新符合红黑树的规则。</p>
<h4 id="调整方法"><a href="#调整方法" class="headerlink" title="调整方法"></a>调整方法</h4><h5 id="变色"><a href="#变色" class="headerlink" title="变色"></a>变色</h5><p>为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。</p>
<p>下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/b33dd4fe9fa1406483100fc8d94756e9.png" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<p>但这样并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/e2c8a86adfdf4c038dfab611a32fca2b.jpeg" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<p>此时仍然没有结束，因为节点25和节点27又形成了两个连续的红色节点，需要继续把节点27从红色变成黑色：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/59ab2094d6b74da3bbb4f26629521b00.png" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<h5 id="旋转"><a href="#旋转" class="headerlink" title="旋转"></a>旋转</h5><h6 id="左旋转"><a href="#左旋转" class="headerlink" title="左旋转"></a>左旋转</h6><p>逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。说起来很怪异，大家看下图：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/1888aa1672284d94af7b731ffe72257e.png" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<p>图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。此为左旋转。</p>
<h6 id="右旋转"><a href="#右旋转" class="headerlink" title="右旋转"></a>右旋转</h6><p>顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。大家看下图：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/12a8cd12919f4b99a2254beda609e5bf.png" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<p>图中，身为左孩子的Y取代了X的位置，而X变成了自己的右孩子。此为右旋转。</p>
<h4 id="实战举栗子"><a href="#实战举栗子" class="headerlink" title="实战举栗子"></a>实战举栗子</h4><p>我们以刚才插入节点21的情况为例：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/ad6dddf3ed144c5b979183f13c290cc2.jpeg" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<p>首先，我们需要做的是变色，把节点25及其下方的节点变色：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/12d9f1e3b7d1446daa1b8d1a48897cde.jpeg" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<p>此时节点17和节点25是连续的两个红色节点，那么把节点17变成黑色节点？恐怕不合适。这样一来不但打破了规则4，而且根据规则2（根节点是黑色），也不可能把节点13变成红色节点。</p>
<p>变色已无法解决问题，我们把节点13看做X，把节点17看做Y，像刚才的示意图那样进行左旋转：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/74f6f8f8355247948495b4b3094f86bc.png" alt="旋转示意图" title>
                </div>
                <div class="image-caption">旋转示意图</div>
            </figure>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/d69e7b48a28f4135a7554c360b0bea5b.jpeg" alt="开始旋转啦" title>
                </div>
                <div class="image-caption">开始旋转啦</div>
            </figure>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/4b323ee47f9d46b781b0ce204d0b79af.jpeg" alt="旋转一" title>
                </div>
                <div class="image-caption">旋转一</div>
            </figure>
<p>由于根节点必须是黑色节点，所以需要变色，变色结果如下：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/4ae94e8a07044050bed14496231392f2.jpeg" alt="旋转后变色" title>
                </div>
                <div class="image-caption">旋转后变色</div>
            </figure>
<p>这样就结束了吗？并没有。因为其中两条路径(17 -&gt; 8 -&gt; 6 -&gt; NIL)的黑色节点个数是4，其他路径的黑色节点个数是3，不符合规则5。</p>
<p>这时候我们需要把节点13看做X，节点8看做Y，像刚才的示意图那样进行右旋转：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/5809321e3f774a578536d629a79b605d.png" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/c0adf7a0db354d2e874343c16f18f422.jpeg" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/d169722adeef4be094064d5dde40d409.jpeg" alt="旋转结果" title>
                </div>
                <div class="image-caption">旋转结果</div>
            </figure>
<p>最后根据规则来进行变色：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="http://5b0988e595225.cdn.sohucs.com/images/20171102/e79b3c4ba10d45d78e281134d454fdbe.jpeg" alt="最终结果" title>
                </div>
                <div class="image-caption">最终结果</div>
            </figure>
<p>如此一来，我们的红黑树变得重新符合规则。这一个例子的调整过程比较复杂，经历了如下步骤：</p>
<blockquote>
<p>$变色 -&gt; 左旋转 -&gt; 变色 -&gt; 右旋转 -&gt; 变色$</p>
</blockquote>
<h4 id="红黑树使用场景"><a href="#红黑树使用场景" class="headerlink" title="红黑树使用场景"></a>红黑树使用场景</h4><p>其应用有很多，比如有JDK的集合类<code>TreeMap</code>和<code>TreeSet</code>底层就是红黑树，在Java8中，<code>HashMap</code>也是用到了红黑树。</p>
<p>😊欢迎关注我的博客😊： <a href="https://lvshen9.github.io/" target="_blank" rel="noopener">Lvshen’s Blog</a></p>

        </div>

        <blockquote class="post-copyright">
    
    <div class="content">
        
<span class="post-time">
    最后更新时间：<time datetime="2017-11-07T06:43:42.638Z" itemprop="dateUpdated">2017-11-07 14:43:42</time>
</span><br>


        
        原文链接：<a href="/2017/11/07/红黑树的变色与旋转/" target="_blank" rel="external">https://lvshen9.gitee.io/2017/11/07/红黑树的变色与旋转/</a>
        
    </div>
    
    <footer>
        <a href="https://lvshen9.gitee.io">
            <img src="/img/avatar.jpg" alt="我的技术小房间">
            我的技术小房间
        </a>
    </footer>
</blockquote>

        
<div class="page-reward">
    <a id="rewardBtn" href="javascript:;" class="page-reward-btn waves-effect waves-circle waves-light">赏</a>
</div>



        <div class="post-footer">
            
	<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/算法/">算法</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/红黑树/">红黑树</a></li></ul>


            
<div class="page-share-wrap">
    

<div class="page-share" id="pageShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=https://lvshen9.gitee.io/2017/11/07/红黑树的变色与旋转/&title=《红黑树的变色与旋转》 — Lvshen's Blog&pic=https://lvshen9.gitee.io/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=https://lvshen9.gitee.io/2017/11/07/红黑树的变色与旋转/&title=《红黑树的变色与旋转》 — Lvshen's Blog&source=为什么需要红黑树？二叉查找树红黑树需要根据二叉查找树的规则生成，那么二叉查找树具备什么特性呢？其特性如下：

左子树上所有结点的值均小于或等于它的根结点的..." data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=https://lvshen9.gitee.io/2017/11/07/红黑树的变色与旋转/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《红黑树的变色与旋转》 — Lvshen's Blog&url=https://lvshen9.gitee.io/2017/11/07/红黑树的变色与旋转/&via=https://lvshen9.gitee.io" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=https://lvshen9.gitee.io/2017/11/07/红黑树的变色与旋转/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>



    <a href="javascript:;" id="shareFab" class="page-share-fab waves-effect waves-circle">
        <i class="icon icon-share-alt icon-lg"></i>
    </a>
</div>



        </div>
    </div>

    
<nav class="post-nav flex-row flex-justify-between">
  
    <div class="waves-block waves-effect prev">
      <a href="/2017/11/19/监控平台配置文件说明/" id="post-prev" class="post-nav-link">
        <div class="tips"><i class="icon icon-angle-left icon-lg icon-pr"></i> Prev</div>
        <h4 class="title">监控平台配置文件说明</h4>
      </a>
    </div>
  

  
    <div class="waves-block waves-effect next">
      <a href="/2017/11/06/前端常见跨域解决方案（全）/" id="post-next" class="post-nav-link">
        <div class="tips">Next <i class="icon icon-angle-right icon-lg icon-pl"></i></div>
        <h4 class="title">前端常见跨域解决方案（全）</h4>
      </a>
    </div>
  
</nav>



    











    <!-- Valine Comments -->
    <div class="comments vcomment" id="comments"></div>
    <script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
    <script src="//unpkg.com/valine@latest/dist/Valine.min.js"></script>
    <!-- Valine Comments script -->
    <script>
        var GUEST_INFO = ['nick','mail','link'];
        var guest_info = 'nick,mail,link'.split(',').filter(function(item){
          return GUEST_INFO.indexOf(item) > -1
        });
        new Valine({
            el: '#comments',
            notify: 'false' == 'true',
            verify: 'false' == 'true',
            appId: "dy9kXHwg5jQUlLryQmpjWRlM-gzGzoHsz",
            appKey: "P9Nh39Ol0JbMMiYqNGHEP3ml",
            avatar: "mm",
            placeholder: "Just go go",
            guest_info: guest_info.length == 0 ? GUEST_INFO : guest_info,
            pageSize: "10"
        })
    </script>
    <!-- Valine Comments end -->







</article>

<div id="reward" class="page-modal reward-lay">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <h3 class="reward-title">
        <i class="icon icon-quote-left"></i>
        谢谢大爷~
        <i class="icon icon-quote-right"></i>
    </h3>
    <div class="reward-content">
        
        <div class="reward-code">
            <img id="rewardCode" src="https://lvshen9.github.io/blog2/pay/weixin.jpg" alt="打赏二维码">
        </div>
        
        <label class="reward-toggle">
            <input id="rewardToggle" type="checkbox" class="reward-toggle-check"
                data-wechat="https://lvshen9.github.io/blog2/pay/weixin.jpg" data-alipay="https://lvshen9.github.io/blog2/pay/zhifu.jpg">
            <div class="reward-toggle-ctrol">
                <span class="reward-toggle-item wechat">微信</span>
                <span class="reward-toggle-label"></span>
                <span class="reward-toggle-item alipay">支付宝</span>
            </div>
        </label>
        
    </div>
</div>



</div>

        <footer class="footer">
    <div class="top">
        
<p>
    <span id="busuanzi_container_site_uv" style='display:none'>
        站点总访客数：<span id="busuanzi_value_site_uv"></span>
    </span>
    <span id="busuanzi_container_site_pv" style='display:none'>
        站点总访问量：<span id="busuanzi_value_site_pv"></span>
    </span>
</p>


        <p>
            
            <span>博客内容遵循 <a rel="license" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">知识共享 署名 - 非商业性 - 相同方式共享 4.0 国际协议</a></span>
        </p>
    </div>
    <div class="bottom">
        <p><span>我的技术小房间 &copy; 2015 - 2020</span>
            <span>
                
                Power by <a href="http://hexo.io/" target="_blank">Hexo</a> Theme <a href="https://github.com/yscoder/hexo-theme-indigo" target="_blank">indigo</a>
            </span>
        </p>
    </div>
</footer>

    </main>
    <div class="mask" id="mask"></div>
<a href="javascript:;" id="gotop" class="waves-effect waves-circle waves-light"><span class="icon icon-lg icon-chevron-up"></span></a>



<div class="global-share" id="globalShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=https://lvshen9.gitee.io/2017/11/07/红黑树的变色与旋转/&title=《红黑树的变色与旋转》 — Lvshen's Blog&pic=https://lvshen9.gitee.io/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=https://lvshen9.gitee.io/2017/11/07/红黑树的变色与旋转/&title=《红黑树的变色与旋转》 — Lvshen's Blog&source=为什么需要红黑树？二叉查找树红黑树需要根据二叉查找树的规则生成，那么二叉查找树具备什么特性呢？其特性如下：

左子树上所有结点的值均小于或等于它的根结点的..." data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=https://lvshen9.gitee.io/2017/11/07/红黑树的变色与旋转/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《红黑树的变色与旋转》 — Lvshen's Blog&url=https://lvshen9.gitee.io/2017/11/07/红黑树的变色与旋转/&via=https://lvshen9.gitee.io" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=https://lvshen9.gitee.io/2017/11/07/红黑树的变色与旋转/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>


<div class="page-modal wx-share" id="wxShare">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <p>扫一扫，分享到微信</p>
    <img src="//api.qrserver.com/v1/create-qr-code/?data=https://lvshen9.gitee.io/2017/11/07/红黑树的变色与旋转/" alt="微信分享二维码">
</div>




    <script src="//cdn.bootcss.com/node-waves/0.7.4/waves.min.js"></script>
<script>
var BLOG = { ROOT: '/', SHARE: true, REWARD: true };


</script>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/main.min.js"></script>


<div class="search-panel" id="search-panel">
    <ul class="search-result" id="search-result"></ul>
</div>
<template id="search-tpl">
<li class="item">
    <a href="{path}" class="waves-block waves-effect">
        <div class="title ellipsis" title="{title}">{title}</div>
        <div class="flex-row flex-middle">
            <div class="tags ellipsis">
                {tags}
            </div>
            <time class="flex-col time">{date}</time>
        </div>
    </a>
</li>
</template>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/search.min.js" async></script>






<script async src="//dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>



<script>
(function() {
    var OriginTitile = document.title, titleTime;
    document.addEventListener('visibilitychange', function() {
        if (document.hidden) {
            document.title = '死鬼去哪里了！';
            clearTimeout(titleTime);
        } else {
            document.title = '(つェ⊂)咦!又好了!';
            titleTime = setTimeout(function() {
                document.title = OriginTitile;
            },2000);
        }
    });
})();
</script>



</body>
</html>
